package arithmetic;

import java.lang.*;
import java.util.*;

/**
 * 插入排序
 */
public class insertion_sorting {
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        int number;
        System.out.println("请输入要排序的个数:");
        number=in.nextInt();
        //直接插入排序
        int []a=new int [number];
        for(int i=0;i<number;i++)
        {
            a[i]=in.nextInt();
        }
        int min=a[0];
            for(int i =1;i < a.length; ++i)//用end的位置控制边界
            {
                //单趟排序
                int end = i - 1 ;//下标减1 便于前面排好的数据与下标为i的数据进行比较 同时保证下面比较end+1 时数组不会越界
                int tmp = a[i];//设定中间变量储存值 便于后面插入
                while( end >= 0 )//循环继续条件
                {
                    if( a[end] > tmp )
                    {
                        a[end+1] = a[end];//移动数据将大的数据放到后面
                        end--;//指向向前移动一位将前一个数与temp比较 也可以保证第一个数大于第二数的时候不会越界
                    }
                    else
                        break;
                }
                a[end+1] = tmp;//插入数据数据或者保持不变 在索引为end 的数字后面插入temp数字
            }
        for (int element : a)
            System.out.println(element);
        }
    }

